정렬 알고리즘 개념 정리

버블정렬 O(n^2)

인접한 두개의 요소를 비교해서 맨 뒤에서 부터 채워넣는 방식

In [2]:
list = [4, 5, 2, 6, 7]

# 1. index 0 에서 시작
# 2. 인접한 두개의 요소를 비교 [a,b]
# 3. b가 크면 a와 위치를 바꿈, 아니면 그대로
# 4. index 뒤로 이동
# 5. 끝에 요소 배치가 완료되었으면 다시 처음으로

def bubble_sort(list):
    for i in range(len(list)):
        for j in range(len(list) - 1):
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
    return list

bubble_sort(list)
[2, 4, 5, 6, 7]

선택정렬 O(n^2)

최소값을 찾아서 맨 앞에서 부터 채워넣는 방식

In [1]:
list = [4, 5, 2, 6, 7]

# 1. [a, b, c ... f] 에서 최소값을 찾는다.
# 2. 찾은 최소값을 맨 앞에 값(a)과 교체
# 3.     [b, c, .. f] 에서 최소값을 찾는다.
# 4. 찾은 최소값을 맨 앞의 값(b)과 교체
# ... 반복

def selection_sort(list):
    for i in range(len(list)):
        min_index = i
        for j in range(i + 1, len(list)):
            if list[j] < list[min_index]:
                min_index = j
        list[i], list[min_index] = list[min_index], list[i]
    return list

selection_sort(list)
[2, 4, 5, 6, 7]

삽입정렬 O(n^2)

전체에서 하나씩 올바른 위치에 삽입하는 방식

In [2]:
list = [4, 5, 2, 6, 7]

# 1. [a, b, c, d, e], 맨 앞에 있는 것은 이미 정렬이 되어있다고 가정
# 2. [a] 에 b 를 넣는다고 생각
# 3. [a, b]
# 4. [a, b] 에 c 를 넣는다고 생각
# 5. [a, c, b]
# 6. 반복...

def insertion_sort(list):
    for i in range(1, len(list)):
        for j in range(i, 0, -1):
            if list[j] < list[j - 1]:
                list[j], list[j - 1] = list[j - 1], list[j]
    return list

insertion_sort(list)
[2, 4, 5, 6, 7]

병합정렬 O(N * logN)

배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘.

list = [4, 5, 2, 6, 7]

# 배열을 반으로 나누기 때문에 시간복잡도 O(logN) * 배열을 합치는 함수 O(N) = O(N * logN)
def merge_sort(list):
    if len(list) <= 1:
        return list
    
    midIndex = len(list) // 2
    left = merge_sort(list[:midIndex])
    right = merge_sort(list[midIndex:])

    return merge(merge_sort(left), merge_sort(right))

# 정렬된 배열 2개를 합치는 함수, 시간복잡도 O(N)
def merge(left, right):
    result = []
    left_idx = 0
    right_idx = 0
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    while left_idx < len(left):
        result.append(left[left_idx])
        left_idx += 1

    while right_idx < len(right):
        result.append(right[right_idx])
        right_idx += 1

    return result

merge_sort(list)
[2, 4, 5, 6, 7]
LinkedIn